1. Field of the Invention
The invention relates to computer systems, and in particular, the generation of fast, optimized code by merging binary translated basic blocks of instructions.
2. Description of Related Art
Each computer architecture includes its own unique instruction set. Computer program instructions that are compiled into executable code for a first source instruction set architecture, such as the Intel.RTM. X86, may undergo a binary translation in order to be compatible with a different target instruction set architecture, such as a reduced instruction-set computer (RISC) or very long instruction word (VLIW) computer architecture.
The translation may be performed by a dynamic translator typically stored in memory. During dynamic translation, instructions are typically translated one basic block of instructions (BB) at a time, and stored in memory at an area allocated for storing translated BBs, such as the Translated Basic Blocks memory location 160, shown in the memory of FIG. 1. Each basic block of instructions includes a contiguous sequence of non-branch instructions (i.e. do not change order of executing instructions) which typically ends with a conditional branch instruction.
An untranslated computer program, such as the Source Program 110 of FIG. 1, consist of several BB's stored in a physical static sequence (e.g., BB.sub.1, BB.sub.2, BB.sub.3 . . . BB.sub.10). The order of executing the BB's can be different from the static sequence. The order of executing the BB's is determined by the behavior of the BB's branch instructions.
For example, if the branch instructions of BB.sub.1 and BB.sub.4 are the only branch instructions taken in the Source Program 110 (i.e. the branch instruction of BB.sub.3 is not taken), the order of execution is BB.sub.1 -BB.sub.3 -BB.sub.4 -BB.sub.10. In the order of Execution, BB.sub.1 and BB.sub.3, as well as BB.sub.4 and BB.sub.10, remain separated in the physical static sequence of the program.
After a BB has been translated, the translated BB is stored in memory. However, the translated BB's may not be stored in the order of the original static sequence of the untranslated Basic Blocks of instructions. Therefore, when executing a translated BB additional time maybe needed to locate the memory address of the translated BB.
In addition, after a BB has been translated, the instructions of the BB are typically rescheduled to accommodate resource and data dependencies among the instructions within the BB. The rescheduling becomes more effective as the number of instructions rescheduled increases. The rescheduling, however, is typically limited to the instructions within one BB, which typically only consist of five to ten instructions.